#include "DoubleLinkList.h"
#include <stdio.h>
#include <stdlib.h>
//创建节点的接口
DLNode* CreateNode(ElementType element)
{
    DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
    if(newNode == NULL)
    {
        printf("create node malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void InitDLlist(DLlist *list)
{
    //将头节点和尾节点初始化为NULL
    list->head = list->tail = CreateNode(NULL);
    list->len = 0;
}

void InsertDLlistTail(DLlist *list, ElementType element)
{
    DLNode *newNode = CreateNode(element);
    if(newNode == NULL)
        return;
    //将尾巴指向插入的节点
    list->tail->next = newNode;
    //将节点指向尾巴
    newNode->prev = list->tail;
    //将尾巴向后移
    list->tail = newNode;
    list->len++;
}

void InsertDLlistHead(DLlist *list, ElementType element)
{
    //防止链表为空的情况(尾插)
    if(list->len == 0)
        InsertDLlistTail(list,element);
    else
    {
        DLNode *newNode = CreateNode(element);
        if(newNode == NULL)
        return;
        //要插入的节点和head->next相连
        newNode->next = list->head->next;
        //要插入的节点和头节点相连
        newNode->prev = list->head;

        //出现连续指向,要注意节点是否存在
        list->head->next->prev = newNode;
        list->head->next = newNode;
        list->len++;
    }    
}

void RemoveByIndex(DLlist *list, int index,void (*freePtr)(ElementType))
{
    if(index < 0 || index >= list->len)
    {
        printf("删除位置非法:%d len : %d\n",index,list->len);
        return;
    }

    //要删除的位置是最后一个 尾巴
    if(index == list->len-1)
    {
        DLNode *Prev = list->tail->prev;
        Prev->next = NULL;
        //询问内存要删除的节点的数据域(void*)是否要清空
        if(freePtr != NULL)
        {
            freePtr(list->tail->data);
        }
        free(list->tail);
        list->tail = Prev;
        list->len--;
    }
    else
    {
        //TravelPoint停在要删除的前一个位置
        DLNode *TravelPoint = list->head;
        for(int i = 0; i < index; i++)
        {
            TravelPoint = TravelPoint->next;
        }
        DLNode *freeNode = TravelPoint->next;
        TravelPoint->next = freeNode->next;
        freeNode->next->prev = TravelPoint; // 一定要注意连续指向的节点是否存在
        if(freePtr != NULL)
        {
            freePtr(freeNode->data);
        }
        free(freeNode);
        list->len--;
    }   
}

void RemoveByElement(DLlist *list, ElementType element, bool (*OperPtr)(ElementType, ElementType), void (*freePtr)(ElementType))
{
    DLNode *TravelPoint = list->head;
    int index = 0;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(OperPtr(TravelPoint->next->data,element) == true)
        {
            //留下这块内存的地址，后续释放，防止内存泄漏
            RemoveByIndex(list,index,freePtr);
        }
        else
        {
            index++;
            //避免要删除的两个相邻的值相等
            TravelPoint = TravelPoint->next;
        }
    }
}

ElementType *FindByIndex(DLlist *list, int index)
{
    if(index < 0 || index >= list->len)
    {
        printf("位置非法的查找:%d len : %d\n",index,list->len);
        return NULL;
    }
    DLNode *TravelPoint = list->head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->data;
}

DLlist FindByElement(DLlist *list, ElementType element, bool (*OperPtr)(ElementType, ElementType))
{
    INITDLLIST(result);
    DLNode *TravelPoint = list->head;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(OperPtr(TravelPoint->next->data,element) == true)
        {
            InsertDLlistTail(&result,TravelPoint->next->data);
        }
        TravelPoint = TravelPoint->next;
    }
    return result;
}

void TravelDLlist(DLlist *list, void (*funcPtr)(ElementType))
{
    if(funcPtr == NULL)
        return;
    DLNode *TravelPoint = list->head->next;
    while(TravelPoint != NULL)
    {
        funcPtr(TravelPoint->data);
        TravelPoint = TravelPoint->next;
    }
    //printf("\n");
}

//交换
void Swap(ElementType *value1,ElementType *value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

//排序
void FastSort(DLNode *start,DLNode *end,bool (*funcPtr)(void*,void *))
{
    if(start == end)
    {
        return;
    }

    DLNode *p1 = start;
    DLNode *p2 = p1->next;

    //循环终止条件
    while(p2 != end)
    {
        //后面的指针的值比基准值小
        if(funcPtr(p2->data,start->data) == true)
        {
            //p1向后移动,把p1和p2的值交换
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        //交换完后,p2继续向后移动
        p2 = p2->next;
    }
    //最后将基准值和p1交换,p1之前的值都比p1小,p2之后的值都比p2大
    Swap(&start->data,&p1->data);
    //经过一轮排序,p1的位置一定在比它小的值末尾,p2一定在比它大的值的末尾
    FastSort(start,p1,funcPtr);
    FastSort(p1->next,p2,funcPtr);
}

void DLlistSort(DLlist *list, bool (*funcPtr)(ElementType, ElementType))
{
    FastSort(list->head->next,NULL,funcPtr);
}

void ClearDLlist(DLlist *list, void (*clearPtr)(ElementType))
{
    while(list->head != NULL)
    {
        DLNode* next = list->head->next;
        if(list->head->data != NULL && clearPtr != NULL)
        {
            clearPtr(list->head->data);
        }
        free(list->head);
        list->head = next;
    }
    
    list->len = 0;
}


